package _14_btree;

import org.junit.Test;

import static org.junit.Assert.assertEquals;


/**
 * @author: mornd
 * @dateTime: 2023/6/17 - 0:58
 */
public class MyTest {
    @Test // 测试叶子节点分裂 t=2
    public void testSplit() {
        /*
                5           2|5
              /  \         / | \
           1|2|3  6       1  3  6

         */
        BTree bTree = new BTree(2);
        BTree.Node root = bTree.root;
        root.keyNumber = 1;
        root.keys[0] = 5;
        root.leaf = false;

        //region build
        BTree.Node left = new BTree.Node(2);
        left.keys[0] = 1;
        left.keys[1] = 2;
        left.keys[2] = 3;
        left.keyNumber = 3;

        BTree.Node right = new BTree.Node(2);
        right.keys[0] = 6;
        right.keyNumber = 1;
        //endregion

        root.children[0] = left;
        root.children[1] = right;

        System.out.println(bTree + "\n");
        bTree.split(left, root, 0);

        System.out.println(bTree);
    }

    @Test // 测试根节点分裂 t=2
    public void testSplit2() {
        /*
            1|2|3         2
                         /\
                        1  3
         */
        BTree bTree = new BTree(2);
        BTree.Node root = bTree.root;
        root.keyNumber = 3;
        root.keys[0] = 1;
        root.keys[1] = 2;
        root.keys[2] = 3;
        bTree.split(root, null, 0);
        System.out.println(bTree);
    }

    @Test // 测试非叶子节点分裂 t=2
    public void testSplit3() {
        /*
                   8                               4|8
                 /   \                           /  |  \
              2|4|6  9          ==>             2   6   9
             /\  /\                            /\  /\
            1 3 5 7                           1 3 5 7
         */
        //region Description
        BTree bTree = new BTree(2);
        BTree.Node root = bTree.root;

        root.keyNumber = 1;
        root.keys[0] = 8;
        root.leaf = false;

        BTree.Node left = new BTree.Node(2);
        left.keyNumber = 3;
        left.leaf = false;
        left.keys[0] = 2;
        left.keys[1] = 4;
        left.keys[2] = 6;
        root.children[0] = left;

        BTree.Node right = new BTree.Node(2);
        right.keyNumber = 1;
        right.keys[0] = 9;
        right.leaf = false;
        root.children[1] = right;

        BTree.Node grandson1 = new BTree.Node(2);
        grandson1.keyNumber = 1;
        grandson1.keys[0] = 1;

        BTree.Node grandson2 = new BTree.Node(2);
        grandson2.keyNumber = 1;
        grandson2.keys[0] = 3;

        BTree.Node grandson3 = new BTree.Node(2);
        grandson3.keyNumber = 1;
        grandson3.keys[0] = 5;

        BTree.Node grandson4 = new BTree.Node(2);
        grandson4.keyNumber = 1;
        grandson4.keys[0] = 7;

        left.children[0] = grandson1;
        left.children[1] = grandson2;
        left.children[2] = grandson3;
        left.children[3] = grandson4;

        System.out.println(bTree + "\n");
        bTree.split(left, root, 0);
        System.out.println(bTree);
        //endregion

        assertEquals("[4, 8]", root.toString());

        assertEquals("[2]", root.children[0].toString());
        assertEquals("[6]", root.children[1].toString());

        assertEquals("[1]", root.children[0].children[0].toString());
        assertEquals("[3]", root.children[0].children[1].toString());

        assertEquals("[5]", root.children[1].children[0].toString());
        assertEquals("[7]", root.children[1].children[1].toString());
    }

    @Test
    public void testPut() {
        BTree bTree = new BTree(2);
        for (int i = 1; i <= 11; i++) {
            bTree.put(i);
        }
        System.out.println(bTree);

        assertEquals("[9]", bTree.root.children[2].children[0].toString());
        assertEquals("[11]", bTree.root.children[2].children[1].toString());
    }

    @Test
    public void testPut2() {
        BTree bTree = new BTree(3);
        for (int i = 1; i <= 21; i++) {
            bTree.put(i);
            System.out.println(bTree + "\n--------------------------------");
        }
    }

    @Test
    public void testRemove() {
        BTree bTree = new BTree(3);
        for (int i = 1; i <= 20; i++) {
            bTree.put(i);
        }
        System.out.println(bTree + "\n");
        for (int i = 20; i > 0; i--) {
            bTree.remove(i);
            System.out.println("key=" + i);
            System.out.println(bTree + "\n-----------------");
        }
    }
}
